home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / graph_alg.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  7.5 KB  |  314 lines
  1. #include <LEDA/graph_alg.h>
  2. #include <LEDA/graph_edit.h>
  3. #include <math.h>
  4.  
  5.  
  6.  
  7. window W;
  8. //window w1(440,440,0,125);
  9.  
  10. void bold_edge(GRAPH<point,int>& G, edge e)
  11. { point p = G[source(e)];
  12.   point q = G[target(e)];
  13.   W.set_mode(xor_mode);
  14.   W.draw_edge_arrow(p,q,blue);
  15.   int save = W.set_line_width(5);
  16.   W.draw_edge(p,q,blue);
  17.   W.set_line_width(save);
  18.   W.set_mode(src_mode);
  19. }
  20.  
  21. void unbold_edge(GRAPH<point,int>& G, edge e)
  22. { int save = W.set_line_width(5);
  23.   point p = G[source(e)];
  24.   point q = G[target(e)];
  25.   W.set_mode(xor_mode);
  26.   W.draw_edge(p,q,blue);
  27.   W.set_line_width(save);
  28.   W.draw_edge_arrow(p,q,blue);
  29.   W.set_mode(src_mode);
  30. }
  31.  
  32. void show_edge_inf(GRAPH<point,int>& G, edge_array<int>& edge_num)
  33. { edge e;
  34.   W.set_mode(xor_mode);
  35.   forall_edges(e,G)
  36.   { point p = G[source(e)];
  37.     point q = G[target(e)];
  38.     W.draw_text((p.xcoord()+q.xcoord())/2, (p.ycoord()+q.ycoord())/2,
  39.                   string("%d", edge_num[e]));
  40.    }
  41.   W.set_mode(src_mode);
  42.  }
  43.  
  44. void show_edge_inf(UGRAPH<point,int>& G, edge_array<int>& edge_num)
  45. { edge e;
  46.   W.set_mode(xor_mode);
  47.   forall_edges(e,G)
  48.   { point p = G[source(e)];
  49.     point q = G[target(e)];
  50.     W.draw_text((p.xcoord()+q.xcoord())/2, (p.ycoord()+q.ycoord())/2,
  51.                   string("%d", edge_num[e]));
  52.    }
  53.   W.set_mode(src_mode);
  54.  }
  55.  
  56.  
  57. void show_node_inf(UGRAPH<point,int>& G, node_array<int>& node_num)
  58. { node v;
  59.   forall_nodes(v,G)
  60.     W.draw_int_node(G[v],node_num[v],violet);
  61. }
  62.  
  63. void show_node_inf(GRAPH<point,int>& G, node_array<int>& node_num)
  64. { node v;
  65.   forall_nodes(v,G)
  66.      W.draw_int_node(G[v],node_num[v],violet);
  67. }
  68.  
  69. void show_two_node_inf(GRAPH<point,int>& G, node_array<int>& node_num1,
  70.                                             node_array<int>& node_num2)
  71. { node v;
  72.   forall_nodes(v,G)
  73.   { string s("%d|%d",node_num1[v],node_num2[v]);
  74.     W.draw_text_node(G[v],s);
  75.    }
  76. }
  77.  
  78. void draw_graph(GRAPH<point,int>& G) 
  79. { node v,w;
  80.   int i = 0;
  81.   forall_nodes(v,G)
  82.    { W.draw_int_node(G[v],i++,yellow);
  83.      forall_adj_nodes(w,v)
  84.         W.draw_edge_arrow(G[v],G[w],blue);
  85.     }
  86. }
  87.  
  88. void draw_graph(UGRAPH<point,int>& G) 
  89. { node v,w;
  90.   int i = 0;
  91.   forall_nodes(v,G)
  92.    { W.draw_int_node(G[v],i++,yellow);
  93.      forall_adj_nodes(w,v)
  94.         W.draw_edge(G[v],G[w],blue);
  95.     }
  96. }
  97.  
  98.  
  99. void generate_graph(GRAPH<point,int>& G)
  100. {
  101.   panel P_gen;
  102.  
  103.   int n = 0;
  104.   int m = 0;
  105.  
  106.   P_gen.int_item("# nodes", n);
  107.   P_gen.int_item("# edges", m);
  108.  
  109.   P_gen.button("random");
  110.   P_gen.button("complete");
  111.   P_gen.button("bi_random");
  112.   P_gen.button("bi_complete");
  113.  
  114.   list<node> A,B;
  115.   node v;
  116.  
  117.   int xmin = (int)W.xmin();
  118.   int ymin = (int)W.ymin();
  119.   int xmax = (int)W.xmax();
  120.   int ymax = (int)W.ymax();
  121.  
  122.   int i = P_gen.open();
  123.  
  124.   switch(i)
  125.   {
  126.     case 0: random_graph(G,n,m);
  127.             break;
  128.     case 1: complete_graph(G,n);
  129.             break;
  130.  
  131.     case 2: random_bigraph(G,n,n,m,A,B);
  132.             break;
  133.  
  134.     case 3: complete_bigraph(G,n,n,A,B);
  135.             break;
  136.    }
  137.  
  138.    if (i > 1)
  139.       { double dy = (ymax-ymin)/(n+1);
  140.         double y = ymin + dy;
  141.         forall(v,A) 
  142.         { G[v] = point(xmin + (xmax-xmin)/4,y);
  143.           y += dy;
  144.          }
  145.         y = ymin + dy;
  146.         forall(v,B) 
  147.         { G[v] = point(xmax - (xmax-xmin)/4,y);
  148.           y += dy;
  149.          }
  150.         }
  151.     else // circular embedding 
  152.        { double R  = (xmax-xmin)/2.5;
  153.          double x0 = (xmax-xmin)/2;
  154.          double y0 = (ymax-ymin)/2;
  155.          point  M(x0,y0);
  156.          double alpha = 0;
  157.          double step  = 2*M_PI/n;
  158.          forall_nodes(v,G)  
  159.          { G[v] = M.translate(alpha,R);
  160.            alpha+=step;
  161.           }
  162.         }
  163.  
  164. }
  165.  
  166.  
  167. main()
  168. {
  169.   panel P("Graph Algorithms");
  170.  
  171.   list<string> alg_menu;
  172.   alg_menu.append(string("topsort"));
  173.   alg_menu.append(string("dfsnum"));
  174.   alg_menu.append(string("components"));
  175.   alg_menu.append(string("strongcomp"));
  176.   alg_menu.append(string("bicomp"));
  177.   alg_menu.append(string("matching"));
  178.  
  179.   string alg = alg_menu.head();
  180.  
  181.   P.string_item("algorithm", alg, alg_menu);
  182.   P.button("file");   // 0
  183.   P.button("gen");    // 1
  184.   P.button("edit");   // 2
  185.   P.button("run");    // 3
  186.   P.button("quit");   // 4
  187.  
  188.   P.display(0,0);
  189.  
  190.   string file      = "graph.1";
  191.  
  192.   panel file_panel("FILE PANEL");
  193.   file_panel.string_item("file", file);
  194.   file_panel.button("load");
  195.   file_panel.button("save");
  196.  
  197.   GRAPH<point,int>  G;
  198.   edge e;
  199.  
  200.   for(;;)
  201.   { 
  202.     W.del_message();
  203.  
  204.     int key = P.read();
  205.  
  206.     if (key == 4) break;
  207.  
  208.     switch(key) 
  209.     {
  210.       case 0: { int b = file_panel.open(); 
  211.                 if (b==0)  // load
  212.                 { W.message(string("loading graph from %s",~file));
  213.                   G.clear();
  214.                   G.read(file);
  215.                   W.clear();
  216.                   draw_graph(G);
  217.                  }
  218.                 if (b==1)  // save
  219.                 { G.write(file);
  220.                   W.message(string("writing graph to %s",~file));
  221.                 }
  222.                 break;
  223.                }
  224.  
  225.       case 1: G.clear();
  226.               generate_graph(G);
  227.               W.clear();
  228.               draw_graph(G);
  229.               break;
  230.  
  231.       case 2: { //graph_edit(w1,G);
  232.                 //W.clear();
  233.                 //draw_graph(G);
  234.                 graph_edit(W,G);
  235.                 break;
  236.                }
  237.  
  238.       case 3: { if (alg == "bicomp")
  239.                 { W.message("BICONNECTED COMPONENTS");
  240.                   UGRAPH<point,int> U = G;
  241.                   edge_array<int> edge_num(U);
  242.                   BICONNECTED_COMPONENTS(U,edge_num);
  243.                   show_edge_inf(U,edge_num);
  244.                   W.read_mouse();
  245.                   show_edge_inf(U,edge_num);
  246.                   break;
  247.                  }
  248.  
  249.                 if (alg == "dfsnum")
  250.                 { W.message("DFS NUMBERING");
  251.                   node_array<int> dfs_num(G);
  252.                   node_array<int> comp_num(G);
  253.                   DFS_NUM(G,dfs_num,comp_num);
  254.                   show_two_node_inf(G,dfs_num,comp_num);
  255.                   W.read_mouse();
  256.                   draw_graph(G);
  257.                   break;
  258.                  }
  259.  
  260.                 if (alg == "components")
  261.                 { W.message("COMPONENTS");
  262.                   UGRAPH<point,int> U = G;
  263.                   node_array<int> node_num(U);
  264.                   COMPONENTS(U,node_num);
  265.                   show_node_inf(U,node_num);
  266.                   W.read_mouse();
  267.                   draw_graph(G);
  268.                   break;
  269.                  }
  270.           
  271.                 if (alg == "strongcomp")
  272.                 { W.message("STRONG COMPONENTS");
  273.                   node_array<int> node_num(G);
  274.                   STRONG_COMPONENTS(G,node_num);
  275.                   show_node_inf(G,node_num);
  276.                   W.read_mouse();
  277.                   draw_graph(G);
  278.                   break;
  279.                  }
  280.  
  281.                 if (alg == "topsort")
  282.                 { W.message("TOPSORT");
  283.                   node_array<int> node_num(G);
  284.                   if (TOPSORT(G,node_num)==false)
  285.                   { W.acknowledge("Graph is cyclic, cannot sort");
  286.                     break;
  287.                    }
  288.                   show_node_inf(G,node_num);
  289.                   W.read_mouse();
  290.                   draw_graph(G);
  291.                   break;
  292.                  }
  293.  
  294.                 if (alg == "matching")
  295.                 { W.message("MAX_CARD_MATCHING");
  296.                   list<edge> L = MAX_CARD_MATCHING(G);
  297.                   forall(e,L) bold_edge(G,e);       
  298.                   W.read_mouse();
  299.                   forall(e,L) unbold_edge(G,e);       
  300.                   break;
  301.                  }
  302.  
  303.                 W.acknowledge(alg + " not found");
  304.                 break;
  305.           
  306.               }
  307.  
  308.     } //switch
  309.  
  310.   } // for(;;)
  311.  
  312.   return 0;
  313. }
  314.